package algorithm._1_Array._1BinarySearch;

/**
 * Created by xiaoxu.
 */
public class BinarySearch {

    private BinarySearch() {
    }

    //时间复杂度 o(log n)
    //int a = l+r;
    // int mid = a / 2;
    public static int binarySearch(Comparable[] arr, int n, Comparable target) {

        int l = 0, r = n - 1; // 在[l...r]的范围里寻找target
        while (l <= r) {    // 当 l == r时,区间[l...r]依然是有效的
            int mid = l + (r - l) / 2;
            if (arr[mid].compareTo(target) == 0) return mid;
            if (target.compareTo(arr[mid]) > 0)
                l = mid + 1;  // target在[mid+1...r]中; [l...mid]一定没有target
            else    // target < arr[mid]
                r = mid - 1;  // target在[l...mid-1]中; [mid...r]一定没有target
        }

        return -1;
    }

    /**
     * 顺序查找法 时间复杂度 o(n)
     * @param arr
     * @param n
     * @param target
     * @return
     */
    public static int orderSearch(Comparable[] arr, int n, Comparable target) {
        for (int i = 0; i < n; i++) {
            if (arr[i].compareTo(target) == 0)
                return i;
        }
        return -1;
    }


    public static void main(String[] args) {


        int n = (int) Math.pow(10, 5);
        Integer data[] = Util.generateOrderedArray(n);

        long startTime = System.currentTimeMillis();
        for (int i = 0; i < n; i++)
            //if (i != binarySearch(data, n, i))
            if (i != orderSearch(data, n, i))
            //if (i != MyBinarySearch.binarySearch(data,i))
                throw new IllegalStateException("find i failed!");
        long endTime = System.currentTimeMillis();

        System.out.println("Binary Search test complete.");
        System.out.println("Time cost: " + (endTime - startTime) + " ms");


    }
}
